package arithmetic_40;

import java.util.ArrayList;
import java.util.List;

public class Solution_23 {

	/**
	 *
	 * 思路1：因为对二叉搜索树做中序遍历后的得到的数据是递增的。所以可以做一次中序遍历，得到的数组，只要确保是递增即可
	 *
	 * 该思路的优化点：用一个前驱节点，替代数组，每次遍历到的节点，都判断是否大于前驱节点
	 *
	 */
	public boolean isValidBST(TreeNode root) {

		// 1、中序遍历，结果存到数组
		List<Integer> list = new ArrayList<Integer>();
		inOrder(root, list);

		// 2、遍历数组，验证数组是否递增
		for (int i = 0; i < list.size() - 1; i++) {
			if (list.get(i) >= list.get(i+1)) {
				return false; //前一个节点大于后一个节点，说明非递增，不是二叉搜索树
			}
		}

		return true;
	}

	/**
	 * 思路2：递归左子树的最小值，右子树的最大值
	 */
	public boolean isValidBST2(TreeNode root) {
		return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	public boolean isValid(TreeNode root, Integer min, Integer max) {

		// 空节点也是二叉搜索树
		if (root == null) {
			return true;
		}

		// 当前值必须在min和max之间，否则说明非法
		if (min != null && root.val <= min) {
			return false;
		}
		if (max != null && root.val >= max) {
			return false;
		}

		// 1、检查左子树：因为左子树的所有节点都应该比root节点小，所以更新他的上界max为当前节点
		// 2、检查右子树：因为右子树的所有节点都应该比root节点大，所以更新他的下界min为当前节点
		return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);

	}


	public void inOrder(TreeNode root, List<Integer> list) {
		if (root == null) {
			return;
		}
		inOrder(root.left,list);
		list.add(root.val);
		inOrder(root.right,list);
	}


	public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}